package com.ting.test.algorithms.大厂刷题班;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

/**
 * 假设所有字符串都是小写字母
 * 假设有个一大字符串str
 * 有一个字符串数组arr,去重非空，且每个字符串都可以使用多次
 * 那么能够拼成str的方法一共有多少种
 * 注意 这里隐藏的含义是每个字符串不能拆开，只能作为整体使用
 */
public class 数组中的单词有多少种拼接方法 {

    public static void main(String[] args) {
        String[] arr = new String[]{"dasa", "sdfsa", "asdf"};
        String str = "asdsafaada";
        int count = process(str, arr);
    }

    private static int process(String str, String[] arr) {
        if (str == null) {
            return 0;
        }
        Set<String> set = new HashSet();
        for (int i = 0; i < arr.length; i++) {
            set.add(arr[i]);
        }
        return f(str, 0, set);//主函数调用的含义就是返回从0到结尾，能够被set字符串全部匹配到的方法数
    }

    /**
     * 该函数的含义是返回从i位置开始到结尾，能够被set中的字符串全部匹配到的方法数
     *
     * @param str
     * @param i
     * @param set
     */
    private static int f(String str, int i, Set<String> set) {
        //base
        if (i == str.length()) {
            //说明真个字符串已经被匹配完了
            return 1;
        }

        int ways = 0;
        for (int end = i; end < str.length(); i++) {
            if (set.contains(str.substring(i, end + 1))) {//如果set中有字符串能够匹配到当前indx中，说明方案可行，否则说明方案是不可行的z
                ways += f(str, end - i, set);
            }
        }
        return ways;

    }
}
